﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LinkedList
{
    public class LinkedList<T> : ICollection<T>
    {
        #region Node<T>
        public class Node<T>
        {
            public T Data { get; set; }
            public Node<T> Next { get; set; }
            public Node<T> Prev { get; set; }

            public Node()
            {
                Data = default(T);
                Next = Prev = null;
            }

            public Node(T Data)
            {
                this.Data = Data;
                Next = Prev = null;
            }
        } 
        #endregion

        private Node<T> head = null;
        private Node<T> tail = null;

        #region Properties
        public bool Empty 
        { 
            get 
            { 
                return head == null; 
            } 
        }

        public T Last
        {
            get
            {
                if (tail == null)
                    throw new Exception("LinkedList<T>.Last, list is empty.");
                return tail.Data;
            }
        }

        public T First
        {
            get
            {
                if (head == null)
                    throw new Exception("LinkedList<T>.First, list is empty.");
                return head.Data;
            }
        } 
        #endregion

        public LinkedList() { }

        #region Methods
        public void AddFirst(T data)
        {
            Node<T> n = new Node<T>(data);
            if (head == null)
                head = tail = n;
            else
            {
                head.Prev = n;
                n.Next = head;
                head = n;
            }
        }
        public void AddLast(T data)
        {
            Node<T> n = new Node<T>(data);
            if (head == null)
                head = tail = n;
            else
            {
                tail.Next = n;
                n.Prev = tail;
                tail = n;
            }
        }
        public void RemoveFirst()
        {
            if (head == null)
                throw new Exception("LinkedList<T>.RemoveFirst(), list is empty.");
            head = head.Next;
            if (head == null)
                tail = null;
            else
                head.Prev = null;
        }
        public void RemoveLast()
        {
            if (head == null)
                throw new Exception("LinkedList<T>.RemoveFirst(), list is empty.");
            tail = tail.Prev;
            if (tail == null)
                head = null;
            else
                tail.Next = null;
        }
        public T Find(T item)
        {
            foreach (var data in this)
            {
                if (data.Equals(item))
                    return data;
            }
            return default(T);
        }
        #endregion

        #region ICollection<T>
        public void Add(T item)
        {
            this.AddFirst(item);
        }

        public void Clear()
        {
            head = tail = null;
        }

        public bool Contains(T item)
        {
            foreach (var data in this)
            {
                if (item.Equals(data))
                    return true;
            }
            return false;
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            foreach (var data in this)
            {
                array[arrayIndex] = data;
                arrayIndex++;
            }
        }

        public int Count
        {
            get 
            {
                int count = 0;
                foreach (var item in this)
                {
                    count++;
                }
                return count;
            }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public bool Remove(T item)
        {
            Node<T> n = head;
            while (n != null)
            {
                if (n.Data.Equals(item))
                {
                    if (head == tail) //Only one Node in list
                    {
                        head = tail = null;
                        return true;
                    }
                    else if (n.Next == null) //Node to remove has no succeeding Node
                    {
                        n.Prev.Next = null;
                        tail = n.Prev;
                        return true;
                    }
                    else if (n.Prev == null) //Node to remove has no preceding  Node
                    {
                        n.Next.Prev = null;
                        head = n.Next;
                        return true;
                    }
                    else //Node to remove is somewhere in the middle of the list
                    {
                        n.Prev.Next = n.Next;
                        n.Next.Prev = n.Prev;
                        return true;
                    }
                }
                n = n.Next;
            }
            return false;
        }

        public IEnumerator<T> GetEnumerator()
        {
            Node<T> n = head;

            while (n != null)
            {
                yield return n.Data;
                n = n.Next;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        } 
        #endregion
    }
}
